The invention relates generally to the field of processor scheduling, and, more specifically, to the field of scheduling the execution of real-time programs and non-real-time programs.
Multitasking operating systems allow a number of different programs to execute xe2x80x9csimultaneouslyxe2x80x9d on one or more processors. Such multitasking operating systems do so by rapidly switching the processor between the execution of multiple programs.
A multitasking operating system may operate on an underlying platform having either one or multiple processors. A single-processor system is referred to as a uniprocessor system. A system having multiple processors is referred to as a multiprocessor system. Having more processors available generally means that more programs can be executed simultaneously on a single system.
An operating system can also have either discrete or continuous clock or timing facility. A continuous-clock system as used herein refers to the lowest granularity of timing at which an item can be scheduled relative thereto being many orders less than the units of work to be scheduled, such that to the system the timing is effectively continuousxe2x80x94that is, any desired start time, stop time, and/or duration of an activity can be specified with accuracy. Conversely, a discrete-clock system as used herein refers to the lowest granularity of timing at which an item can be scheduled relative thereto being on about the same order as the units of work to be scheduled, such that to the system the timing appears discretexe2x80x94that is, any desired start time, stop time, and/or duration of an activity cannot be specified with as great as accuracy as in a continuous system. For example, a continuous-clock system may allow for timing to be specified in microsecond increments, while the items to be scheduled may have durations on the order of milliseconds, such that relative to the scheduled items, the clock appears continuous. As a further example, a discrete-clock system may allow for timing to be specified only in millisecond increments (which can be referred to as the discrete clock time-keeping interval)xe2x80x94the same order of timing for which the scheduled items may be specified in, such that relative to the scheduled items, the clock is discrete, which is a barrier for providing accurately scheduled items as desired.
Furthermore, a discrete-clock system may also be either periodic or aperiodic. A periodic-clock system has timing interrupts at regular intervals, for example, at times 0, 1, 2, 3, 4, etc. That is, a periodic clock provides scheduling interrupts on a periodic basis. Conversely, an aperiodic-clock system allows for the skipping of unwanted or undesired intervals. Several potential interrupt intervals may be skipped, such that intervals are instead provided at, for example, 0, 1, 7, 9, 10, 11, 17, 19, etc.
A single program, also known as a xe2x80x9cprocess,xe2x80x9d may have one or more threads. The word xe2x80x9cthreadxe2x80x9d as used herein means the finest scheduleable unit of execution. A thread is typically represented by a data structure called an execution context, which contains state information about the execution of the thread, such as register and stack contents. When the operating system suspends a thread in favor of the execution of another thread, it copies the information from the registers and stack to the thread""s execution context. When the operating system subsequently reselects the thread for execution after suspending another thread, it copies the information in the thread""s execution context back to the actual registers and stack. In this way, the thread continues executing with the same register and stack contents as when it was suspended. One or more threads often belong to a process, which corresponds to a body of code and which may own certain single-process resources, such as blocks of memory. While processes and programs can be viewed as roughly equivalent, in some cases, multiple processes may be said to constitute a program, and in other cases, a process may include several programs.
The process of determining which threads to execute at which times is generally termed xe2x80x9cschedulingxe2x80x9d a computer system""s CPU. The way in which scheduling is performed can significantly impact a user""s perception of whether individual threads are performing adequately. Modem multimedia applications, for example, often require substantial processor time, and appear to proceed slowly or in a jerky fashion if they do not receive the required processor time.
Real-time programs are programs that have an understanding of their execution performance needs and timeliness requirements, and can interact with a real-time interface of the operating system to make those execution performance needs and timeliness requirements known to the operating system, such as multimedia applications and industrial applications. Real-time programs can each have a number of threads of execution, grouped under one or more xe2x80x9cactivities,xe2x80x9d or aspects of the real-time program whose overall execution performance needs differ. Each activity may submit a processor reservation specifying the amount of processor time that its threads collectively need on an ongoing basis. Each thread may itself submit time constraints specifying that it needs a certain amount of processor time by a certain deadline. Reservations and time constraints are known collectively as xe2x80x9cexecution timing requests.xe2x80x9d
Certain conventional schedulers handle reservations and time constraints by maintaining the information relating to the reservations and time constraints for use in identifying the next thread to execute on an ad hoc basis each time the processor becomes available for reassignment to a new thread. This conventional xe2x80x9cad hocxe2x80x9d approach to scheduling has several disadvantages. First, completely reevaluating the relative urgencies of all of the existing threads each time the processor becomes available for reassignment often consumes substantial execution time, which makes this execution time unavailable to the real-time programs. Additionally, the approach cannot guarantee at the time a reservation or time constraint is submitted that the reservation or time constraint will be honored. The ad hoc approach can also cause unnecessarily frequent thread switches, thereby reducing the efficiency gains resulting from caching information relating to the executing thread. Further, reservations, while honored for specific periods of time under the ad hoc approach, are not executed with the regularity necessary to honor the reservations over every window of time.
In the copending and coassigned application entitled xe2x80x9cProviding Predictable Scheduling of Programs Using A Repeating Precomputed Schedule,xe2x80x9d filed on Jan. 9, 1997, and assigned Ser. No. 08/781,106, of which the current application is a continuation-in-part, a real-time scheduler is described. However, the real-time scheduler has three primary limitations: first, it operates only a uniprocessor system, not on multiprocessor systems; second, it uses a continuous aperiodic clock, not a discrete clock, and in particular not the more common periodic clock; and, third, it does not utilize the existing scheduler of an operating system such as Windows NT, but rather specifies its own scheduler. For these and other reasons, there is a need for the present invention.
The present invention provides predictable scheduling of real-time programs and non-real-time programs using a repeating precomputed schedule. In accordance with the invention, a thread scheduling software facility (xe2x80x9cthe schedulerxe2x80x9d) overcomes the shortcomings of the conventional ad hoc approach to scheduling by utilizing a precomputed schedule that specifies the future execution of activities and threads having outstanding time constraints, which significantly reduces the processing required to (A) identify the next thread to execute when the processor becomes available and (B) determine the amount of time for which to execute the identified thread. As a result, the process of identifying the next thread to execute and determining the amount of time for which to execute the identified thread can be performed in a bounded amount of time that is independent of the number of threads and activities being scheduled. The precomputed schedule allows the scheduler to assess the feasibility of reservations and time constraints when they are submitted, and immediately refuse any nonfeasible reservations and time constraints. The precomputed schedule also allows the scheduler to guarantee that reservations will be honored with regularity. The precomputed schedule further allows the scheduler to maximize the length of individual intervals assigned to each thread, thereby allowing each thread to make more efficient use of caches. The scheduler further enables blocked activities to receive extra processing time when they are unblocked. The scheduler further effectively schedules the simultaneous execution of real-time and non-real-time programs on the same processor. The scheduler further is able to effectively schedule non-real-time programs in the complete absence of real-time programs, reservations, and constraints.
The precomputed schedule is in one embodiment represented as a directed acyclic graph of nodes, each node corresponding to an execution interval of a specified length, that is incrementally traversed to determine which activity to execute next. (As discussed herein, xe2x80x9cexecuting an activityxe2x80x9d means executing one or more threads belonging to the activity.) Each node may either be dedicated to an activity, such that its interval is used to execute that activity, or designated as a xe2x80x9cfree node,xe2x80x9d whose interval may be used to execute any activity. A complete traversal of the graph is made by traversing, in turn, each path from a root node to one of a group of leaf nodes. The sum of the lengths of the intervals of the nodes in each such path is equal. The number of paths that pass through each node determine the frequency with which its interval recurs while traversing the graph.
The scheduler incorporates reservations in the scheduling graph by dedicating one or more nodes of the graph to the activity submitting the reservation. Nodes are selected that are on enough paths to be executed frequently enough to satisfy the reservation, and whose intervals are long enough to satisfy the reservation. When the scheduler traverses to a node dedicated to the activity, the scheduler executes one or more threads of that activity. The scheduler incorporates time constraints in the scheduling graph by allocating to the time constraints specific traversals through nodes of the graph that are either dedicated to the activity of the thread submitting the time constraint or that are free nodes. When the scheduler performs the allocated traversals through these nodes, the thread submitting the time constraint is executed.
The scheduler is able to run on any of the following: a uniprocessor continuous-clock system; a multiprocessor continuous-clock system; a uniprocessor discrete-but-aperiodic-clock system; a multiprocessor discrete-but-aperiodic-clock system; a uniprocessor periodic-clock system; and, a multiprocessor periodic-clock system. Furthermore the system may have an existing scheduler than can be used by the scheduler of embodiments of the invention. In the case of multiprocessor systems, there may be one scheduling graph for each processor, or a scheduling graph may traverse multiple processors. In the case of discrete-clock systems, start and end times for reservations and constraints are adjusted to compensate for the granularity of the clock of the system.